package day07;

public class 打家劫舍二 {
    /*public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0]; // 边界条件

        // 情况1：偷第0家，不能偷第n-1家（环形限制）
        int[] f1 = new int[n]; // f1[i]：偷第i家时的最大金额
        int[] g1 = new int[n]; // g1[i]：不偷第i家时的最大金额
        f1[0] = nums[0];
        for (int i = 1; i < n - 1; i++) { // 跳过最后一家
            f1[i] = g1[i - 1] + nums[i];
            g1[i] = Math.max(f1[i - 1], g1[i - 1]);
        }
        int ret1 = Math.max(f1[n - 2], g1[n - 2]); // 结果取倒数第二家的最大值

        // 情况2：不偷第0家，可以偷第n-1家
        int[] f2 = new int[n]; // 新的数组，避免复用
        int[] g2 = new int[n];
        g2[0] = 0; // 明确初始化
        for (int i = 1; i < n; i++) { // 正常处理到最后一家
            f2[i] = g2[i - 1] + nums[i];
            g2[i] = Math.max(f2[i - 1], g2[i - 1]);
        }
        int ret2 = Math.max(f2[n - 1], g2[n - 1]);

        return Math.max(ret1, ret2);
    }*/

    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0)
            return 0;
        // 情况1：偷第0家，不能偷最后一家（范围：[2, n-2]）
        int case1 = nums[0] + dajiajieshe(nums, 2, n - 2);

        // 情况2：不偷第0家，可以偷最后一家（范围：[1, n-1]）
        int case2 = dajiajieshe(nums, 1, n - 1);
        return Math.max(case1, case2);
    }

    public int dajiajieshe(int[] nums, int start, int end) {
        if (start > end) {
            return 0;
        }
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        // 初始化
        f[start] = nums[start];
        g[0] = 0;
        for (int i = start + 1; i <= end; i++) {
            f[i] = g[i - 1] + nums[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        return Math.max(f[end], g[end]);
    }
}
